#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

typedef int ElemType;
typedef struct NodeList{
	ElemType data;
	struct NodeList *next;
}LNode,*LinkList;

struct NodeList* createNodeList(ElemType arr[],int n)
{
	LinkList head;
	LNode *p1,*p2;
	int i;
	head=NULL;
	for(i=0;i<n;i++)
	{
		p1=(LNode*)malloc(sizeof(LNode));//分配空间
		p1->data=arr[i];
		//从无到有
		if(head==NULL)
		{
			head=p1;
		}
		else
		{
			p2->next=p1;
		}
		p2=p1;
	}
	p2->next=head;
	
	return p2;
}
/*
解决方案
  普通解法

  我们可能用链表的方法去模拟这个过程:
  N个人看作是N个链表节点，节点1指向节点2，节点2指向节点3，……，
  节点N-1指向节点N，节点N指向节点1，这样就形成了一个环。
  然后从节点1开始1、2、3……往下报数，每报到M，就把那个节点从环上删除。
  下一个节点接着从1开始报数。最终链表仅剩一个节点。
  它就是最终的胜利者。
*/

//约瑟夫环实现一：

void Joseph(LinkList p,int m,int n)
{
	LinkList q;
	int i;
	q=p;
	int t=m;
	if(n==0)return;//循环链表节点数为0
	m%=n;
	if(m==0)m=n;
	for(i=1;i<=m;i++)
	{
		p=q;
		q=q->next;
	}

	//printf("%d\n",q->data);
	
	//指针域变换
	p->next=q->next;
	//打印切除的数据
	printf("%d ",q->data);
	free(q);
	Joseph(p, t, n-1);
}
int main()
{
	ElemType arr[]={4,7,5,9,3,2,6,1,8};
	int n=sizeof(arr)/sizeof(arr[0]);
	LNode *head;
	head=createNodeList(arr,n);
	printf("请输入第一次计数值：");
	int m;
	scanf("%d",&m);
	//Joseph(head,m,n);
	Solution
	return 0;
}
